// 岛屿数量： https://leetcode-cn.com/problems/number-of-islands/submissions/
package main

// 之前用python就做过一遍了

// 图算法深度优先遍历
func numIslands(grid [][]byte) int {
	var dfs func(x, y int)
	dir := [][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
	n, m := len(grid), len(grid[0])

	// 深度优先，找到一个块儿
	dfs = func(x, y int) {
		if grid[x][y] == '0' {
			return
		}
		// byte 类型数组，这里注意要用单引号
		grid[x][y] = '0'

		for _, ac := range dir {
			newX := ac[0] + x
			newY := ac[1] + y
			// 剪枝
			if newX >= 0 && newY >= 0 &&
				newX < n && newY < m {
				dfs(newX, newY)
			}
		}
	}

	cnt := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' {
				// 调用深度优先遍遍历，找到这一块陆地
				dfs(i, j)
				cnt += 1
			}
		}
	}
	return cnt
}
